package xin.luna.structs;

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

/**
 * 队列的链表实现
 *
 * @param <Item>
 */
public class QueueLinkedTable<Item> {
  public static void main(String[] args) {
    QueueLinkedTable<String> queue = new QueueLinkedTable<>();

    while (!StdIn.isEmpty()) {
      String item = StdIn.readString();
      if (!item.equals("-")) {
        queue.enqueue(item);
      } else if (!queue.isEmpty()) {
        StdOut.print(queue.dequeue() + "   ");
      }
    }

    StdOut.println("(" + queue.size() + " left on queue)");
  }

  private Node first;

  private Node last;

  private int length;

  public boolean isEmpty() {
    return 0 == length;
  }

  public int size() {
    return length;
  }

  public void enqueue(Item item) {
    Node node = new Node();
    node.item = item;

    if (isEmpty()) {
      first = node;
    } else {
      last.next = node;
    }

    last = node;

    length++;
  }

  public Item dequeue() {
    Item item = first.item;
    first = first.next;
    length--;

    return item;
  }

  private class Node {
    Item item;
    Node next;
  }
}
